package org.hot100.h019;

/**
 * @Author: wjy
 * @Date: 2021/12/9 16:23
 */
public class Solution {

    public static void main(String[] args) {

        ListNode listNode5 = new ListNode(5);
        ListNode listNode4 = new ListNode(4, listNode5);
        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);

        Solution solution = new Solution();
        ListNode listNode = solution.removeNthFromEnd2(listNode1, 1);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }

    }

    // 1 2 3 4 5
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 当head长度为1， n = 1时 ListNode temp = new ListNode(0);作用体现，否则不需要也可
        ListNode temp = new ListNode(0);
        temp.next = head;
        ListNode slow = temp, fast = temp;

        while (n != 0) {
            fast = fast.next;
            n--;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;

        return temp.next;
    }

    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode node = new ListNode();
        node.next = head;
        ListNode slow = node, fast = node;
        while (n-- > 0) {
            fast = fast.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return node.next;
    }

}
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }